By

Contents
  1. 1. 0x01 malloc_chunk的基本结构
  2. 2. 0x02 chunk的复用
  3. 3. 0x03 Bin
    1. 3.1. 一．概述
    2. 3.2. 二．分类
      1. 3.2.1. 1. fast bins
      2. 3.2.2. 2. unsorted bins
      3. 3.2.3. 3. small bins
      4. 3.2.4. 4. large bins
  4. 4. 0x04 三种特殊的chunk
    1. 4.1. top chunk
    2. 4.2. mmaped chunk（略）
    3. 4.3. last remainder chunk（略）
  5. 5. 综上
    1. 5.1. 内存分配：_int_malloc
    2. 5.2. 内存回收：free
  6. 6. 分配区
    1. 6.1. main_arena

复习堆的时候发现自己对于堆结构，空间申请与释放，函数调用掌握的还是不够透彻，所以再重新复习一遍堆的数据结构 o3o 也发现了一些以前搞错了很多，害…
本文只捡练了一些（以32位系统为例,64位基本都是对应size*2）

0x01 malloc_chunk的基本结构

（使用中/未被free）

（空闲chunk/free之后）

  1. size字段的低三个比特位对chunk的大小没有影响，他们从高到底分别表示：
    • NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程（main_arena），1 表示不属于，0 表示属于。
    • ID_MAPPED，记录当前 chunk 是否是由 mmap 分配的。（chunk空闲时，M不存在）
    • PREV_INUSE，记录前一个chunk是否被分配。1表示被分配，0表示没有。堆的第一个chunk所记录的prev_inuse位默认为1
  2. fd_nextsize bk_nextsize在chunk空闲时才使用，（Large bin中特有）暂不讲解。
  3. 一般情况下，物理相邻的两个空闲chunk会被合并为一个chunk，堆管理器会通过prev_size字段及size字段合并两个物理相邻的空闲chunk。

0x02 chunk的复用

空闲时，一个chunk至少需要4个size_t（4B）大小的空间（prev_size, size, fd, bk）共16B，且chunk的大小要对齐到8B。
当一个chunk处于使用状态时，它的下一个chunk的prev_size无效，该prev_size域被当前chunk使用。（可以理解为，当chunk在使用时，在二进制文件中执行，而不归共享库管理，下一个chunk的prev_size域直接分配给当前chunk，可以使内存空间高效利用，也省去重新分配空间的麻烦）
一个使用中的chunk的大小in_use_size = (用户申请大小 + 8 - 4) align to 8B
+8是存储prev_size和size
-4是“借”了下一个chunk的prev_size
最终分配的chunk_size = max(in_use_size, 16)

0x03 Bin

一．概述

  • 用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
  • ptmalloc将相似大小的chunk用双向链表链接，此链表称为bin。ptmalloc一共维护了128个bin，并使用一个数组来存储这些bin
  • free掉一个chunk时根据chunk大小加入到对应的bin中。


bin[128]中0和127不使用

二．分类

1. fast bins

不大于max_fast（64B）的chunk被释放后，首先会被放到fastbins中，fastbins中的chunk不改变它的Prev_inuse标志，也就无法被合并。
当用户需要的chunk大小 < max_fast时，ptmalloc会首先判断fastbin中相应的bin中是否有对应大小的空闲块（这里比较的是无符号整数），如果有，直接从fastbin头结点开始取chunk。free之后如果再次malloc相同size，会申请到同一块内存。如果没有才会查找bins中的空闲chunk。
在某个特定的时候，ptmalloc会遍历fastbins中的chunk，将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin中，然后再将unsortedbin中的chunk加入bins。

fast bin为单链表。采用LIFO（Last In First Out）。fastbins cache了 small bins的前7个大小的空闲chunk，对于 SIZE_SZ 为 4B 的平台【16B，24B，32B，40B，48B，56B，64B】；对 于 SIZE_SZ 为 8B 的平台【32B，48B，64B，80B，96B，112B，128B】

当每次释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 64k 时，就认为内存碎片可能比较多了，就需要 把 fast bins 中的所有 chunk 都进行合并，以减少内存碎片对系统的影响

2. unsorted bins

如果被用户释放的chunk > max_fast（64B），或者fastbins中的空闲chunk合并后，这些chunk首先会被放入unsorted bin
malloc时如果fastbin中没有合适的chunk，就会在unsorted bin中查找合适的。如果unsorted bin中没有合适的chunk，就将unsorted bin中的chunk放到所属的bin中再分配。
可以把unsorted bins理解为缓冲区。

unsorted bin为bin[1]，其中的chunk没有排序，大小不限制，双链表，成环。采用FIFO。

3. small bins

small bin为索引2到63，大小为（2 * SIZE_SZ * ndx）（即 size < 512B），双链表，成环。采用FIFO。
实际共62个bin，同一个small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小32 位相差 8 字节【16B, 24B, 32B, …, 504B】，64 位相差 16 字节【32B, 48B, 64B, …, 1008B】
分配时采用精确匹配。

4. large bins

large bin为索引64到126，大小为[512,512+64)（即 size >= 512B）。
一共包括63个bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致。
以32位平台（SIZE_SZ = 4B）为例：

组 数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 不限制

large bins 中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。
分配时采用最近匹配。

——上述这些 bin 的排布都会遵循一个原则：任意两个物理相邻的空闲 chunk 不能在一起。

需要注意的是，并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的 chunk先放到 fast bins 的容器内。而且，fastbin 容器中的 chunk 的使用标记总是被置位的，所以不满足上面的原则。

0x04 三种特殊的chunk

并不是所有的chunk都按照上面的方式组织。以下是三种特殊的chunk，他们不属于任何bins。

top chunk

对于非主分配区预先从mmap分配一块较大的sub-heap，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。【因为内存是按地址从底向高进行分配的】
这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就重新分配一个sub-heap，并将top chunk迁移到新的sub-heap上再分配。
top chunk分配内存会使top chunk减小。如果回收的chunk恰好与top chunk相邻，那么合并成新top chunk使top chunk变大。
如果free时回收的内存大于某个阈值，且top chunk大小也超过的收缩阈值，ptmalloc就会收缩sub-heap。如果top chunk包含了整个sub-heap，ptmalloc会调用munmap把整个sub-heap返回操作系统。

主分配区是唯一能够映射进程heap区域的分配区（有点难理解。。。）在 main arena 中通过 sbrk 扩展收缩 heap，ptmalloc会预先分配一块较大的空闲内存（heap）
主分配区的top chunk第一次malloc时会分配一块(chunk_size + 128KB) align 4KB大小的空间作为初始heap，用户从top chunk分配内存时，可直接取出一块给用户。如果top chunk中没有空闲内存，ptmalloc会调用sbrk()将进程heap边界brk上移，然后修改top chunk大小。回收时，回收的内存恰好与top chunk相邻则合成新top chunk。
如果free时回收的内存大于某个阈值，且top chunk大小也超过的收缩阈值，会收缩内存，但至少保留一个页大小的空闲内存，从而把内存归还操作系统。

mmaped chunk（略）

chunk足够大时，以上的都不能满足分配需求时，ptmalloc会使用mmap直接使用内存映射来将页映射到进程空间。这样分配的chunk在被free时将直接接触映射，将内存归还给操作系统，若再次对这样的内存引用将导致segmentation fault。

last remainder chunk（略）

需要分配一个small chunk，但small bins中找不到合适的chunk，如果last remainder chunk的大小 > 所需的small chunk大小，就将它分裂成两个chunk，其中一个chunk返回用户，另一个变成新的last remainder chunk。

综上

内存分配：_int_malloc

根据size

  • 获取分配区的锁（略，想了解看源码分析）
  • 将用户请求的大小转换为实际需要分配的chunk_size
  • fastbin range：chunk_size <= max_fast，从fast bin中查找是否有合适的chunk。
    • 找到，分配结束。
    • 未找到 ⬇
  • small bin range：chunk_size < 512B，先从small bin查找（small bin按照size排好，查找更快）按照size从对应具体的small bin的尾部找到恰好满足大小的chunk。
    • 找到，分配结束。
    • 未找到 ⬇
  • ptmalloc首先遍历fast bins中的chunk，将相邻chunk合并，并链接到unsorted bin。
  • 遍历unsorted bin。
    • 如果unsorted bin只有一个chunk，并且该chunk在上次分配时被使用，所需分配的chunk大小属于small bins，且该chunk大小 >= 需要分配的大小，直接切割，分配结束。（丢，好绕）
    • 否则，根据chunk大小放入small bins或large bins中。⬇
  • large bin range：从large bin 中查找满足条件且最小的chunk。
    • 有则切分，剩下的部分链接回bins中，剩余的放入unsorted bin//这是ptmalloc机制，他在分配large chunk时会先对堆中的碎片chunk进行合并，以便减少堆中的碎片
    • 未找到 ⬇
  • 从top chunk切割
    • 满足，分配结束
    • 不满足 ⬇
  • 当topchunk也无法满足时，如果是主分配区，调用sbrk()增加top chunk大小。如果是非主分配区，调用mmap()
    【mmap的具体分配方法 略】

内存回收：free

    1. 获取分配区锁
    1. 检测传入free的指针是否为0
    • 是，直接return
    • 否，⬇
    1. 是否是mmap分配
    • 是，释放mmap的chunk
    • 否，⬇
    1. size是否属于fast bin且chunk并不位于heap顶部，也就是不与top chunk相邻
    • 是，插入fast bin，return
    • 否，⬇
    1. 查看前一个chunk是否free
    • 是，合并，⬇
    1. 查看下一个chunk是否为top chunk
    • 是，合并，更新top chunk大小，⬇
    • 否，->7
    1. 查看下一个chunk是否free
    • 是，合并
    1. 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD（默认 64KB）
    • 是，触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被 遍历，并与相邻的空闲 chunk 进行合并，合并后的 chunk 会被放到 unsorted bin 中。 fast bins 将变为空，⬇
    1. 判断 top chunk 的大小是否大于 mmap 收缩阈值（默认为 128KB）
    • 是，对 于主分配区，则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的 128KB 空间是不会归还的，ptmalloc 会一直管理这部分内存，用于响应用户的分配 请求；如果为非主分配区，会进行 sub-heap 收缩，将 top chunk 的一部分返回给操 作系统，如果 top chunk 为整个 sub-heap，会把整个 sub-heap 还回给操作系统。

释放结束，从 free() 函数退出。可以看出，收缩堆的条件是当前 free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k，并且要 top chunk 的大 小要达到 mmap 收缩阈值，才有可能收缩堆

分配区

arena的个数是跟系统中处理器核心个数相关

1
2
3
4
For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

main_arena

main_arena表示主分配区，任何进程有且仅有一个全局的主分配区

参考：CTF-wiki堆，glibc内存管理ptmalloc2源码分析